package com.algorithm.greedy;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class Greedy {
    public static void main(String[] args) {
        //创建广播电台并存入Map中
        HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
        //将各个电台放入到broadcasts
        HashSet<String> hashSet1 = new HashSet<> ( );
        hashSet1.add ("北京");
        hashSet1.add ("上海");
        hashSet1.add ("天津");
        HashSet<String> hashSet2 = new HashSet<> ( );
        hashSet2.add ("广州");
        hashSet2.add ("北京");
        hashSet2.add ("深圳");
        HashSet<String> hashSet3 = new HashSet<> ( );
        hashSet3.add ("成都");
        hashSet3.add ("上海");
        hashSet3.add ("杭州");
        HashSet<String> hashSet4 = new HashSet<> ( );
        hashSet4.add ("上海");
        hashSet4.add ("天津");
        HashSet<String> hashSet5 = new HashSet<> ( );
        hashSet5.add ("杭州");
        hashSet5.add ("大连");
        //加入到map
        broadcasts.put ("K1", hashSet1);
        broadcasts.put ("K2", hashSet2);
        broadcasts.put ("K3", hashSet3);
        broadcasts.put ("K4", hashSet4);
        broadcasts.put ("K5", hashSet5);

        HashSet<String> selected = selectedBroadcast(broadcasts);
        selected.forEach(System.out::println);

    }
    private static HashSet<String> selectedBroadcast(HashMap<String,HashSet<String>> broadcasts){
        //allAreas 存放所有的地区，每次选中每个电台后，在其中移除该电台所覆盖的范围
        HashSet<String> allAreas = getAllAreas(broadcasts);
        //存放选择电台的集合
        HashSet<String> selected = new HashSet<>();
        //临时集合，用于存放在遍历电台的过程中，电台覆盖地区和所有电台中还未被覆盖地区的交集
        HashSet<String> tempSet = new HashSet<>();

        //每加入一个电台以后，就将所有地区中该电台所覆盖的方位去除，一直循环到全部去除为止
        while(allAreas.size() != 0){
            //存放覆盖范围最多的电台
            String maxKey = null;
            int count = 0;
            int size = 0;
            //遍历所有电台
            for(String key : broadcasts.keySet()){
                //每次遍历将tempSet置空
                tempSet.clear();;
                //当前电台所覆盖的地区
                HashSet<String> areas = broadcasts.get(key);
                tempSet.addAll(areas);
                //求交集
                tempSet.retainAll(allAreas);
                size = tempSet.size();
                if(maxKey != null){
                    HashSet<String> temp = broadcasts.get(maxKey);
                    temp.retainAll(allAreas);
                    count = temp.size();
                }
                //获取当前集合中涵盖未加入的地区的最多的电台,贪心算法的体现
                if(size > 0 && (maxKey == null || count < size)){
                    maxKey = key;
                }
            }
            //遍历完以后得到涵盖未覆盖地区最多的电台，移除这些地区
            if(maxKey!=null){
                selected.add(maxKey);
                allAreas.removeAll(broadcasts.get(maxKey));
            }
        }
        return selected;
    }


    private static HashSet<String> getAllAreas(HashMap<String,HashSet<String>> broadcasts){
        HashSet<String> allAreas = new HashSet<>();
        for(Map.Entry<String,HashSet<String>> entry:broadcasts.entrySet()){
            for(String area:entry.getValue()){
                allAreas.add(area);
            }
        }
        return allAreas;
    }
}
